package leetcode.hot100;

/**
 * leetcode-hot100: 旋转图像
 * 测试链接: https://leetcode.cn/problems/rotate-image/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 给定一个 n x n 的二维矩阵表示一个图像，将图像顺时针旋转90度(在原地旋转图像，不使用额外空间)
 */
public class RotateImage {

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        /**
         找规律得到 位于(i, j)的元素旋转后会去到(j, n - i - 1)
         可以通过两次翻转得到
         (i, j) -> (j, i) -> (j, n - 1 - i)
         */
        //将矩阵进行转置 matrix[i][j] -> matrix[j][i]
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        //行翻转：将每一行与对称位置的元素交换 row[j] -> row[n - j - 1]
        for(int[] row : matrix){
            for(int j = 0; j < n / 2; j++){
                int tmp = row[j];
                row[j] = row[n - j - 1];
                row[n - j - 1] = tmp;
            }
        }
    }
}
